基于Redis Cluster的分布式布隆过滤器

发表于   |   分类于   |     |   阅读次数

一、设计目标

  1. Redis分布式布隆过滤器。
  2. 用户使用透明。(无需关心内部路由、存储细节)
  3. 简单易用(如同使用本地布隆过滤器)。
  4. 支持多种API和批量操作。
  5. 支持多种hash函数。
  6. 高性能、低错误率。

二、基本架构

  1. 两个输入参数：期望插入个数、期望错误概率
  2. 布隆过滤器概率公式计算两个参数：总位图大小、哈希函数迭代次数
  3. 每个Redis的位图设置为100KB：计算布隆过滤器的个数
  4. 根据元素的哈希值，将添加和是否包含请求路由到Redis各个位图上

例如 add(“element-100”)操作的伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
//计算crc16
int hashcode = crc16("element-100");
//计算element-100所在的布隆过滤器索引
int bloomFilterIndex = hashcode % bloomFilterNum(需要的布隆过滤器个数)；
//指定索引的布隆过滤器
String bloomFilterKey = "basename:" + bloomFilterIndex;
//遍历执行murmur3，进行setbit操作
for (int i = 0;i < getHashIterations();i++){
    int hash = murmur3("element-100");
    redis.setbit(bloomFilterKey, hash, 1);
}

三、快速使用

该功能内置在CacheCloud客户端，无需引入其他依赖

1
2
3
4
5
6
7
8
9
10
11
<dependency> 
    <groupId>com.sohu.tv</groupId> 
    <artifactId>cachecloud-client-redis</artifactId> 
    <version>1.6.1-SNAPSHOT</version> 
</dependency> 
<repositories> 
    <repository> 
        <id>sohu.nexus</id> 
        <url>http://index.tv.sohuno.com/nexus/content/groups/public</url>
    </repository> 
</repositories>

快速使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
long appId = xx;
PipelineCluster pipelineCluster = ClientBuilder.redisCluster(appId).build();// rediscluster客户端
String bloomFilterName = "cc-bloom-filter";// 布隆过滤器名
long expectedInsertions = 100000000;// 预计插入条数(例如1个亿)
double falseProbability = 0.0001;// 预计错误率(例如万分之一)
// 构建布隆过滤器
BloomFilter<String> bloomFilter = new BloomFilterBuilder(pipelineCluster, bloomFilterName, expectedInsertions, falseProbability).build();
// 添加
bloomFilter.add("a");
bloomFilter.add("b");
bloomFilter.add("c");
bloomFilter.add("d");
// 包含检测
// true
System.out.println(bloomFilter.contains("c"));
// false
System.out.println(bloomFilter.contains("zz"));

四、API说明

1. 参数说明

1
public BloomFilterBuilder(PipelineCluster pipelineCluster, String name, long expectedInsertions, double falseProbability)
必需参数：
参数名 含义 说明
pipelineCluster redisCluster客户端 可以通过appid构造
name 布隆过滤器名 唯一
expectedInsertions 预计插入的条数 最大不能超过1000亿
falseProbability 预计错误率 有关布隆过滤器错误率，可以查看维基百科
可选参数：
参数名 含义 说明 默认值
HashFunction hashFunction 哈希算法 目前支持CRC32、Murmur2、Murmur3三种算法(支持扩展)。 使用Murmur3哈希算法
int childBloomMaxSize 子布隆过滤器位数 1千万(约1MB)

例如使用方法如下

1
2
3
//使用crc32
HashFunction crc32 = new CRC32HashFunction();
BloomFilter<String> bloomFilter = new BloomFilterBuilder(pipelineCluster, bloomFilterName, expectedInsertions, falseProbability).setHashFunction(crc32).build();

2. 相关API说明

(1) 添加

1
boolean add(T object);

(2) 批量添加

1
boolean batchAdd(List<T> objectList);

(3) 查看包含

1
boolean contains(T object);

(4) 批量查看包含

1
Map<T, Boolean> batchContains(List<T> objectList);

(5) 清除布隆过滤器

1
void clear();

(6) 布隆过滤器几个参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 预期插入数量
 */
long getExpectedInsertions();
/**
 * 预期错误概率
 */
double getFalseProbability();
/**
 * 布隆过滤器总长度
 */
long getSize();
/**
 * hash函数迭代次数
 */
int getHashIterations();
/**
  * 子布隆过滤器个数
  */
int getChildBloomNumber();

五、相关测试

1
redis：10.17.XX.XX：18个主节点
测试插入数据量 bloomfilter分片大小 批量提交条数 耗时 QPM 占用空间/对象数 网络流量
4000w(4个线程并行) 1000万(1MB) 5000 24分钟 2100w/min
35w/s		 3.47G/1920个 1100k
4000w(4个线程并行) 5000w(5MB) 5000 12分钟 4200w/min
70w/s		 3.03G/396个 2300k
4000w(4个线程并行) 1个亿(10MB) 5000 11分钟 4750w/min
80w/s		 3.01G/193个 2600K

初步结论

1
2
1. 单个布隆过滤器越大，吞吐越大（减少了路由次数）
2. 集群规模越大，吞吐越大

六、相关改进

  1. 支持多种Redis类型
  2. Murmur3是耗时和错误率较低布隆过滤器函数(查的一组测试数据)，具体有待测试。